package com.ljx.offer;

import java.util.Queue;
import java.util.Stack;

/**
 * @author 李捷禧
 * Date: 2023/4/2
 * ClassName: C_31
 */

public class C_31 {
    /**
     * 优化后的，省了stack的空间
     * 还节省出栈入栈的时间
     * 时间复杂度降为0ms
     * @param pushed
     * @param popped
     * @return
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0;
        int j = 0;
        for (int num : pushed) {
            pushed[i] = num;
            while (i >= 0 && pushed[i] == popped[j]){
                i--;
                j++;
            }
            i++;
        }
        return i == 0;
    }

    /**
     * 使用栈的性质
     * @param pushed
     * @param popped
     * @return
     */
    public boolean validateStackSequences1(int[] pushed, int[] popped) {
        if (popped.length != pushed.length) return false;
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}